package pri.zjy.string;

/**
 * @author zhangjy
 * @description 验证回文串
 * @date 2025/4/2 12:06
 */
public class IsPalindrome_125 {

    public static void main(String[] args) {
        IsPalindrome_125 isPalindrome125 = new IsPalindrome_125();
//        String s = " ";
        String s = "A man, a plan, a canal: Panama";
        System.out.println(isPalindrome125.isPalindrome(s));
        System.out.println(isPalindrome125.isPalindrome2(s));
    }

    /**
     * 参考官解；
     * 双指针，调用API判断字母是否为数字、字母
     */
    public boolean isPalindrome2(String s) {
        int i = 0, j = s.length() - 1;
        char left, right;
        while (i < j) {
            left = s.charAt(i);
            // left不是目标字符
            if (!Character.isLetterOrDigit(left)) {
                i++;
                continue;
            }
            right = s.charAt(j);
            // right不是目标字符
            if (!Character.isLetterOrDigit(right)) {
                j--;
                continue;
            }

            // left、right都是目标字符，则判断是否相同
            if (Character.toLowerCase(left) != Character.toLowerCase(right)) return false;

            i++;
            j--;
        }

        return true;
    }

    /**
     * 个解：
     * <p>
     * 思路：
     * 双指针，判断合法字符是否相同（合法字符指字母、数字）
     *  <p>
     * T(n) = O(n)，其中n为字符串s的长度
     * S(n) = O(1)。
     */
    public boolean isPalindrome(String s) {
        // 双指针遍历，对比两个字符是否相同，若出现不同则返回false；大写字母转为小写，非字母、数字跳过
        int i = 0, j = s.length() - 1;
        char left, right;
        while (i < j) {
            left = getChar(s, i);
            right = getChar(s, j);

            if (!checkNumber(left) && (!checkLowLetter(left) || checkHighLetter(left))) {
                // left非字母、数字
                i++;
            } else if (!checkNumber(right) && (!checkLowLetter(right) || checkHighLetter(right))) {
                // right非字母、数字
                j--;
            } else {
                // 是目标字符，则判断是否相同
                if (left != right) return false;

                i++;
                j--;
            }

        }

        return true;
    }

    public boolean checkNumber(char c) {
        return (int) c >= 48 && (int) c <= 57;
    }

    public boolean checkLowLetter(char c) {
        return (int) c >= 97 && (int) c <= 122;
    }

    public boolean checkHighLetter(char c) {
        return (int) c >= 64 && (int) c <= 90;
    }

    public char getChar(String s, int index) {
        char c = s.charAt(index);
        int ascii = c;
        // 字母、数字才处理
        if (checkNumber(c) || checkLowLetter(c) || checkHighLetter(c)) {
            // 大写转为小写
            if (checkHighLetter(c)) {
                c = (char) (97 + (ascii - 65));
            }
        }
        return c;
    }

}
